1. Field of the Invention
The present invention relates to a fuzzy backward reasoning system for inferring causes from results and an expert system utilizing the same. More specifically, the present invention is concerned with a reasoning system capable of making inference on a real time basis as well as a real-time expert system utilizing the same.
2. Description of the Related Art
As a method of inferring causes from results on the basis of imprecise knowledge of a sympton, (i.e., result and a relation between each cause and each result, as with the case of a medical diagnosis or a fault diagnosis, there is known a fuzzy backward reasoning method in which solution of an inverse problem of fuzzy correspondence is determined. Although many proposals have been made in conjunction with this method, there can be mentioned among them the proposal disclosed in an article by Tukamoto, Y. and Tashiro, T. entitled "Method of Solution to Fuzzy Inverse Problem" (Transactions of The Society of Instrument and Control Engineers, Vol. 15, No. 1, pp. 21-25, 1979) as the one in which adaptability to practical problems is taken into consideration. Before entering into details of the prevent invention, the fuzzy theory which is handled in the present application will briefly be described together with the fuzzy correspondence inverse problem and a method of solution thereof disclosed in the article cited above.
A set of those elements x of a universal set X which are fuzzy or uncertain as to whether belong to the set is referred to as a fuzzy set A. Such a fuzzy set A can be defined by giving the elements x degrees or extents to which the elements x are contained in the set A. A function capable of giving or determining the degree mentioned above is referred to as the membership function and represented by .mu..sub.A (x). This function .mu..sub.A (x) has a property defined as follows: EQU 0.ltoreq..mu..sub.A (x).ltoreq.1
For the universal set X, fuzzy sets A and B, a membership function .mu..sub.A (x) (where x .epsilon.X), there may be defined operations which are mentioned below:
Universal set: .mu..sub.x (x)=1 .sub.x .epsilon. X PA0 Empty set: .mu..sub..phi. (x)=0 PA0 Complementary set A: .mu..sub.A (x)=1-.mu..sub.A (x) PA0 Sum set: .mu..sub.A U.sub.B =min [.mu..sub.A (x), .mu..sub.B (x)] PA0 Product Set: .mu..sub.A.andgate.B =min [.mu..sub.A (x), .mu..sub.B (x)] PA0 Equal relationship: A=B.rarw..mu..sub.A (x)=.mu..sub.B (x) PA0 Containing relatinship: A B.rarw..mu..sub.A (x)=.mu..sub.B (x) PA0 Law of double negation: A=A ##EQU1##
It should however be noted that neither law of the excluded middle nor law of the contradiction which can be applied to an ordinary set can be applied to the fuzzy set. In other words, EQU A.orgate.A.noteq.X A.andgate.A.noteq..phi.
In the fuzzy set A, EQU A.alpha..perspectiveto.{x.vertline..mu..sub.A (x)&gt;.alpha.}; .alpha..epsilon.[0, 1] EQU A.alpha..perspectiveto.{x.vertline..mu..sub.A (x).gtoreq..alpha.}; .alpha..epsilon.[0, 1]
are referred to as strong .alpha.-cut and weak .alpha.-cut, respectively, which are graphically represented, in FIGS. 1A and 1B of the accompanying drawings, respectively.
Truth values imprecisely represented by not a numerical interval form as in the classical logic and the many-valued logic but a linguistic form such as "true", "very true", etc. are referred to as the linguistic truth values or LTV for short. These linguistic truth values (LVTs) may be represented by a fuzzy set on a truth value space [0, 1].
Now, let's consider a method of giving a numerical interval to the linguistic truth value or LTV and assume, by way of example, that a numerical interval be given to the LTV of "true". To this end, a membership function is given to the LTV "true". The membership function may be selected arbitrarily. It is assumed that the membership function is of a linear line form, as illustrated in FIG. 2 of the accompanying drawings. By cutting the membership function at .alpha., i.e., the .alpha.-cut, the numerical interval for the LTV of "true" is determined. By way of example, assuming that .alpha.=0.8, then a numerical interval [0.8, 1] can be determined for the LTV of "true" by the .alpha.-cut, as shown in FIG. 2.
Next, the fuzzy correspondence inverse problem will be considered.
Let's represent sets which contain two different types of events, e.g., items of cause and items of sympton, respectively, as follows: EQU X={x.sub.i .vertline.i=1, . . . , m{ EQU Y={y.sub.j .vertline.j=1, . . . , n}
In that case, the fuzzy sets A and B for which the abovementioned sets are the universal sets, respectively, can be written as follows: ##EQU2## where a.sub.i and b.sub.j represent the degrees to which elements x.sub.i and y.sub.j are contained in the fuzzy sets A and B, respectively.
The fuzzy sets A and B can conveniently be represented in terms of vectors of membership grades as follows:
a=(a.sub.1, . . . , a.sub.m) PA1 b=(b.sub.1, . . . , b.sub.n) PA1 A.smallcircle.C=B PA1 a.smallcircle.R=b
When X represents a universal set of prerequisite conditions, e.g., cause items and Y represents a universal set of conclusions or results, e.g., sympton items, there may be conceived a diagnostic system for deriving the conclusions (results) from the prerequisite conditions. There exist causalities between the individual items x.sub.i of the prerequisite conditions and the individual items y.sub.i of the conclusions (results).
Thus, a fuzzy set C on the XY-space can be written as follows: ##EQU3## where .gamma..sub.ij represents the degrees to which the element (x.sub.i, y.sub.j) belong to the fuzzy set C. Let's express a matrix with m.times.n elements containing .gamma..sub.ij as an i-th row and j-th column element as follows: EQU R={.gamma..sub.ij }
When a fuzzy composition of the fuzzy set A and the fuzzy set C results in a fuzzy set B, this may be written as
wherein an operational rule referred to as a fuzzy relational equation and given by
can be applied, where a.sub.i, b.sub.j .gamma..sub.ij .epsilon.[0, 1] and "602 " represents a max-min composition, i.e. .sub.i V {a.sub.i .andgate..gamma..sub.ij }=b.sub.j, where .orgate. and .andgate. represent "max" and "min", respectively.
Thus, the inverse problem of the fuzzy relational equation can be said to be a problem of "determining all elements of a fuzzy set a which satisfy the relational equation of a.smallcircle.R=b, when a fuzzy relation R is given together with the individual elements of a fuzzy set b in terms of numerical values, respectively, of the interval [0, 1]".
In this conjunction, it is noted that the fuzzy relation can be determined by the relation of the fuzzy set B to the fuzzy set A. Thus, the fuzzy relation can be represented by mapping as follows: EQU R:P(X).fwdarw.P(Y)
On the other hand, fuzzy correspondence is determined by correspondence of the fuzzy set B of a fuzzy set to the fuzzy set A and may thus be expressed by mapping: EQU .gamma.: P(X).fwdarw.P(P(Y))
where P(X) represents a family of all the fuzzy sets on X.
Further, the fuzzy set B can be written as follows: EQU B={(y.sub.j, b.sub.j)}
where b.sub.j represent the degrees by which the element y.sub.j belong to the fuzzy set B and can be given by a fuzzy set in the interval [0, 1]. An n-dimensional vector containing b.sub.j as the j-th element is written as follows: EQU b=(b.sub.1, . . . , b.sub.n) [0, 1].sup.n
Thus, when the fuzzy set C on the XY-space is given, then one fuzzy correspondence .GAMMA. is determined. In this conjunction, the fuzzy set C may be written as follows: EQU C={(x.sub.i, y.sub.j), .gamma..sub.ij }
where .gamma..sub.ij represent degrees by which the element (x.sub.i, y.sub.j) belong to the fuzzy set C and which can be represented by a fuzzy set in [0, 1]. Let's express a matrix with m.times.n elements containing an element .gamma..sub.ij as the i-th row and j-th column element as follows: EQU R={.gamma..sub.ij } [0, 1].sup.mxn
Thus, it is safe to say that the inverse problem of fuzzy correspondence can be reduced to a problem of "determining an inverse mapping .GAMMA..sup.-1 (b) of fuzzy correspondence when b [0, 1].sup.n and R [0, 1].sup.mxn are given as the grades of symptons and the causalities between the causes and the symptons, respectively," where b is a vector representation of the fuzzy set B and R is a matrix representation of the fuzzy set C.
A method of solution of the fuzzy a correspondence inverse problem is proposed in Tsukamoto et al's article recited hereinbefore. According to the proposal, a .alpha.-cut set of the fuzzy correspondence inverse mapping is determined by solving the inverse problem of a.smallcircle.R=b, where EQU a={a.vertline. R, b; R.epsilon.R, b.epsilon.b, a.smallcircle.R=b}
In the above exprssion, R={.gamma..sub.ij } and b=(b.sub.1, . . . , b.sub.n) represent a matrix and a vector containing as respective elements the sets of intervals of real numbers in [0, 1] corresponding to R.alpha. and b.alpha. (.alpha.-cut sets of R and b, respectively). Further, b.epsilon.b and R.epsilon.R represent .sub.j, b.sub.j .epsilon. b.sub.j and .sub.i, .sub.j, .gamma..sub.ij .epsilon. .gamma..sub.ij, respectively.
In the following table, there are summarized comparisons between the inverse problem of fuzzy relational equation and tmhe inverse problem of fuzzy correspondence.
______________________________________ Fuzzy Relation Fuzzy Correspondence Inverse Problem Inverse Problem ______________________________________ Certainty of real values in fuzzy set R in Causality between [0, 1] [0, 1] Cause and Symptom Grade of Symptom real values in fuzzy set b in [0, 1] [0, 1] ______________________________________ A model utilizing the fuzzy correspondence is more flexible when compared with a model utilizing the fuzzy relational equation.
Now, let's consider a method of solving the inverse problem of fuzzy correspondence.
First, .epsilon.-composition and .epsilon.-composition are defined.
For two interval value sets [a, b], [c, d] [0, 1], ##EQU4## where .phi. represents the empty set.
FIG. 3 is a flow chart for illustrating a method of solving an inverse problem of fuzzy correspondence proposed by Tsukamoto et al in their article recited hereinbefore.
The solution algorithm proposed by Tsukamoto et al will now be described.
At a step 1, matrixes U={u.sub.ij } and V={v.sub.ij } each having (m.times.n) elements are determined, where EQU u.sub.ij =.gamma..sub.ij .epsilon.b.sub.j and EQU v.sub.ij =.gamma..sub.i .epsilon.b.sub.j
When it is determined at a step 2 that .sub.j, .sub.i, u.sub.ij =.phi., decision is made that no solutionexists, and the processing comes to an end.
At a step 3, a matrixes W.sup.k ={w.sup.k ij} having (m.times.n) elements are determined, and individual elements of each matrix W.sup.k are givenfor every column j, as follows: ##EQU5## where .sub.li represents selection of only one from i's satisfying u.sub.ij .noteq..phi.. Accordingly, the matrixes W.sup.k exist for the number of combinations determined in accordance with the selection of i. Such combinations is indexed by the symbol "k".
At a step 4, a solution a.sup.k is determined, where EQU a.sup.k =(a.sup.k.sub.1, a.sup.k.sub.2 , . . . , a.sup.k.sub.m) ##EQU6##
At a step 5, it is checked whether k is "0". If the decision results in "Y" indicating "true", decision is made that no solution exists, and then the processing comes to an end.
At a step 6, solution a is determined in accordance with ##EQU7## EQU K={k.vertline. .sub.i ; a.sup.k.sub.i .noteq..phi.}
As will be appreciated from the foregoing, the hitherto known method of solving the inverse problem of fuzzy correspondence is disadvantageous in that the amount of theoretical computation increases in proportion to m.sup.m+1 x n because of necessity of preparing an enormous number of W.sup.K matrices as the number of the causes (m) and the symptons (n) increases, thereby requiring lots of time for the computation. For this reason, the problem solving method of the prior art suffers from a difficulty that the method is difficult to be applied to an inference engine of a real time expert system.